package com.mystudy.leetcode.problem.tree.p_700;

import com.mystudy.leetcode.base.TreeNode;

/**
 * @program: infoalgorithm
 * @description: 二叉搜索树中的搜索
 * @author: zhouzhilong
 * @create: 2019-07-23 16:36
 **/
public class Solution {
    /**
     * 正常遍历,效率非常低
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode node = search(root, val);
        return node;
    }

    private TreeNode search(TreeNode node, int val) {
        if (node == null) {
            return null;
        }

        if (node.val == val) {
            return node;
        } else {
            TreeNode left = search(node.left, val);
            TreeNode right = search(node.right, val);

            if (left != null) {
                return left;
            }
            if (right != null) {
                return right;
            }
            return null;
        }
    }


    /**
     * 因为是二叉搜索树,可以使用中序遍历的思路，减掉不必要的遍历
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST２(TreeNode root, int val) {
        TreeNode node = search(root, val);
        return node;
    }

    private TreeNode search２(TreeNode node, int val) {
        if (node == null) {
            return null;
        }

        if (node.val < val) {
            TreeNode right = search(node.right, val);
            return right;
        } else if (node.val > val) {
            TreeNode left = search(node.left, val);
            return left;
        } else {
            return node;
        }
    }
}
